class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    // 插入方法
    public void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode node, int val) {
        // 如果当前节点为空，创建新节点
        if (node == null) {
            node = new TreeNode(val);
            return node;
        }

        // 如果值小于当前节点，递归插入左子树
        if (val < node.val) {
            node.left = insertRec(node.left, val);
        }
        // 如果值大于当前节点，递归插入右子树
        else if (val > node.val) {
            node.right = insertRec(node.right, val);
        }

        return node;
    }

    // 查找方法
    public boolean search(int val) {
        return searchRec(root, val);
    }

    private boolean searchRec(TreeNode node, int val) {
        // 如果当前节点为空或值等于当前节点，返回结果
        if (node == null || node.val == val) {
            return node != null;
        }

        // 如果值小于当前节点，递归查找左子树
        if (val < node.val) {
            return searchRec(node.left, val);
        }
        // 如果值大于当前节点，递归查找右子树
        return searchRec(node.right, val);
    }
} 